package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Q23 {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode fakeNode = new ListNode(-213123);
        ListNode curr = fakeNode;

        // 堆的元素是2维数组,[链表序号,链表元素值]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                ListNode currNode = lists[i];
                pq.add(new int[]{i, currNode.val});
            }
        }

        while (!pq.isEmpty()) {
            // 取一个出来
            // 添加到后面
            // 更新第i个链表的头指针
            int[] poll = pq.poll();
            ListNode currentListHead = lists[poll[0]];
            curr.next = currentListHead;
            curr = curr.next;
            if (currentListHead.next != null) {
                lists[poll[0]] = currentListHead.next;
                pq.add(new int[]{poll[0], currentListHead.next.val});
            }

        }

        return fakeNode.next;
    }

    public static void main(String[] args) {
        ListNode node11 = new ListNode(1);
        ListNode node12 = new ListNode(4);
        ListNode node13 = new ListNode(5);
        ListNode node21 = new ListNode(1);
        ListNode node22 = new ListNode(3);
        ListNode node23 = new ListNode(4);
        ListNode node31 = new ListNode(2);
        ListNode node32 = new ListNode(6);
        node11.next = node12;
        node12.next = node13;
        node21.next = node22;
        node22.next = node23;
        node31.next = node32;

        ListNode[] listNodes = new ListNode[]{node11, node21, node31};
        ListNode[] listNodes2 = new ListNode[2];
        Q23 twoThree = new Q23();
        System.out.println(twoThree.mergeKLists(listNodes));
    }

}
